#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include "buddy.h"

using namespace std;

// constructor
Buddy::Buddy(unsigned long size){
	Buddy::memPtr = malloc(size);
	Buddy::root = new Block;
	Buddy::root->size = size;
	Buddy::root->location = memPtr;
	//printf("Buddy system starting at location: %p\n", memPtr);
}

// destructor
Buddy::~Buddy(){
	free(Buddy::memPtr);
}

// prints the tree
void Buddy::printTree(){
	printf("print tree (preorder traversal)\n\tkey: <size>[/ = split][* = allocated]\n");
	stack<Block *> nodes;
        nodes.push(Buddy::root);
 
        Block *currentBlock;
 
	// preorder traversal
        while (!nodes.empty()) {
                currentBlock = nodes.top();
		nodes.pop();

		printf("\t\t%lu", currentBlock->size);
		if(currentBlock->allocated)
			printf("*");
		if(currentBlock->split)
			printf("/");		
		printf("\n");

                Block *right = currentBlock->right;
                if (right != NULL) {
                        nodes.push(right);
                }
                Block *left = currentBlock->left;
                if (left != NULL) {
                        nodes.push(left);      
                }
        }
}

// find min that is >= specified size
Block * Buddy::findMin(unsigned long size){
	stack<Block *> nodes;
        nodes.push(Buddy::root);
	min = Buddy::root; 
        Block *currentBlock;
 
	// preorder traversal
        while (!nodes.empty()) {
                currentBlock = nodes.top();
		nodes.pop();
		
		if((currentBlock->size >= size) && (currentBlock->size < min->size) && (currentBlock->allocated == false) && (currentBlock->split == false))
			min = currentBlock;

                Block *right = currentBlock->right;
                if (right != NULL) {
                        nodes.push(right);
                }
                Block *left = currentBlock->left;
                if (left != NULL) {
                        nodes.push(left);      
                }
        }
}

// allocate given size
Block * Buddy::my_malloc(unsigned long size){
	findMin(size);
	int twiceSize = size << 1; // multiply by 2 using bit-shift

	// if the min block is < twice the requested size, allocate it
	if(min->size < twiceSize){
		min->allocated = true;
		return min;	
	}
	// else split the block
	else{
		while(min->size >= twiceSize){
			min = split(min);
		}
		min->allocated = true;
		return min;
	}
}

// free a block
void Buddy::my_free(Block *nodeID){
	Block *buddy = (nodeID == (nodeID->parent)->left ? (nodeID->parent)->right : (nodeID->parent)->left);
	
	// while the node's buddy is not split or allocated, delete the node and it's buddy	
	// if node is it's parent's left node	
	if(buddy && !buddy->split && !buddy->allocated){	
		while(nodeID != Buddy::root && buddy && !buddy->split && !buddy->allocated){
			(nodeID->parent)->right = NULL;
			(nodeID->parent)->allocated = false;
			(nodeID->parent)->split = false;
			(nodeID->parent)->left = NULL;

			nodeID = nodeID->parent;
		
			// if we aren't at the root yet
			if(nodeID != Buddy::root){
				buddy = (nodeID == (nodeID->parent)->left ? (nodeID->parent)->right : (nodeID->parent)->left);			
			}
		}
	}
	else
		nodeID->allocated = false;
}

// split two blocks and return left child
Block * Buddy::split(Block *nodeID){
	nodeID->split = true;
	int halfSize = nodeID->size >> 1; // divide by 2 using bit-shift
	Block *buddy1 = new Block(); Block *buddy2 = new Block();
	buddy1->size = halfSize; buddy2->size = halfSize;
	buddy1->parent = nodeID; buddy2->parent = nodeID;
	buddy1->location = nodeID->location; buddy2->location = (nodeID->location)+halfSize;
	nodeID->left = buddy1; nodeID->right = buddy2;
	return buddy1;
}
